package main.Q1301_1400;

import java.util.TreeMap;

public class Q1361_1370 {
    public static void main(String[] args) {
        System.out.println("Question1361：");
        System.out.println("Question1362");
        System.out.println("Question1363：");
        System.out.println("Question1364：");
        System.out.println("Question1365：有多少小于当前数字的数字");
        System.out.println("Question1366：");
        System.out.println("Question1367：二叉树中的列表");
        System.out.println("Question1368：");
        System.out.println("Question1369：");
        System.out.println("Question1370：");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question1365 {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int[] result = new int[nums.length];
        for (int i=0;i< nums.length;i++) {
            int count=0;
            for (int key : map.keySet()) {
                if (key >= nums[i]) {
                    break;
                }
                count+=map.get(key);
            }
            result[i]=count;
        }
        return result;
    }
}

class Question1367{
    public boolean process(ListNode curList,TreeNode curRoot){//判断左右子树节点匹配
        if (curList==null) return true;
        if (curRoot==null) return false;
        ListNode tempList=curList;
        if (curList.val!=curRoot.val) return false;
        else tempList=tempList.next;
        boolean flagLeft=process(tempList,curRoot.left);
        boolean flagRight=process(tempList,curRoot.right);
        return flagLeft||flagRight;
    }
    public boolean isSubPath(ListNode head, TreeNode root) {//判断以当前节点开始匹配
        if (head==null) return true;
        if (root==null) return false;
        return process(head,root)||isSubPath(head,root.left)||isSubPath(head,root.right);
    }
}